#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>void read(T &x){char CH=getch();int fl=1;x=0;while(CH>'9'||CH<'0'){if(CH=='-')fl=-1;CH=getch();}while(CH<='9'&&CH>='0'){x=x*10+CH-48;CH=getch();}x*=fl;}
	template<typename T>void read_s(T &x){x="";char CH=getch();while(!(CH>='a'&&CH<='z')&&!(CH>='A'&&CH<='Z'))CH=getch();while((CH>='a'&&CH<='z')||(CH>='A'&&CH<='Z')){x+=CH;CH=getch();}}
	template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char CH) {if(p3-obuf<(1<<21))*p3++=CH;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=CH;}
	char CH[100];
	template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)CH[++top]=x%10+48,x/=10;while(top)putch(CH[top]),top--;}
	template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);putch(' ');write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,c;
int a[1000005];
int bkt[1000005];
//int f[5005][5005];
namespace Shiroha
{
	struct segt
	{
		int val,mn,tagp,tagc,taga;
		int mxv,mx;
	}t[1000005<<2];
	#define ls (root<<1)
	#define rs (root<<1|1)
	#define mid ((l+r)>>1)
	inline void update(int root)
	{
		t[root].val=min(t[ls].val,t[rs].val);
		t[root].mn=min(t[ls].mn,t[rs].mn);
		t[root].mxv=max(t[ls].mxv,t[rs].mxv);
		t[root].mx=max(t[ls].mx,t[rs].mx);
	}
	inline void pushp(int root,int v){t[root].tagp+=v;t[root].val+=v*t[root].mn;t[root].mxv+=v*t[root].mx;}
	inline void pusha(int root,int v){t[root].taga+=v;t[root].val+=v;t[root].mxv+=v;}
	inline void pushc(int root,int v){t[root].taga=t[root].tagp=0;t[root].val=t[root].mxv=t[root].tagc=v;}
	inline void down(int root)
	{
		if(t[root].tagc!=-1) pushc(ls,t[root].tagc),pushc(rs,t[root].tagc);
		if(t[root].tagp) pushp(ls,t[root].tagp),pushp(rs,t[root].tagp);
		if(t[root].taga) pusha(ls,t[root].taga),pusha(rs,t[root].taga);
		t[root].tagp=t[root].taga=0;t[root].tagc=-1;
	}
	void bld(int root=1,int l=1,int r=n)
	{
		if(l==r) return t[root].mn=t[root].mx=bkt[l],void();
		bld(ls,l,mid);bld(rs,mid+1,r);
		update(root);
	}
	void add(int x,int y,int p,int v,int root=1,int l=1,int r=n)
	{
		if(x>y) return;
		if(l>=x&&r<=y) return pushp(root,p),pusha(root,v),void();
		down(root);
		if(x<=mid) add(x,y,p,v,ls,l,mid);
		if(y>mid) add(x,y,p,v,rs,mid+1,r);
		update(root);
	}
	void cov(int x,int y,int v,int root=1,int l=1,int r=n)
	{
		if(x>y) return;
		if(l==r) return t[root].val=min(t[root].val,v),void();
		if(l>=x&&r<=y) 
		{
			if(t[root].mxv<=v) return;
			if(t[root].val>=v) return pushc(root,v),void();
			down(root);
			if(t[rs].val>=v) pushc(rs,v),cov(x,y,v,ls,l,mid);
			else cov(x,y,v,rs,mid+1,r);
			update(root);
			return;
		}
		down(root);
		if(x<=mid) cov(x,y,v,ls,l,mid);
		if(y>mid) cov(x,y,v,rs,mid+1,r);
		update(root);
	}
	int query(int x,int y,int root=1,int l=1,int r=n)
	{
		if(l>=x&&r<=y) return t[root].val;
		down(root);
		int res=1e18;
		if(x<=mid) res=min(res,query(x,y,ls,l,mid));
		if(y>mid) res=min(res,query(x,y,rs,mid+1,r));
		return res;
	}
}using namespace Shiroha;
signed main()
{
	freopen("minimize.in","r",stdin);
	freopen("minimize.out","w",stdout);
	read(n,c);
	for(int i=1;i<=n;i++) read(a[i]),bkt[i]=a[i];
	sort(bkt+1,bkt+n+1);
	int tot=unique(bkt+1,bkt+n+1)-bkt-1;
//	memset(f,0x3f,sizeof f);
//	for(int i=1;i<=n;i++) f[0][i]=0;
	bld();
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(bkt+1,bkt+tot+1,a[i])-bkt;
//		for(int j=1;j<a[i];j++) f[i][j]=f[i-1][j]+c;
//		for(int j=a[i];j<=tot;j++) f[i][j]=f[i-1][j]+bkt[j]-bkt[a[i]];
//		for(int j=tot;j;j--) f[i][j]=min(f[i][j],f[i][j+1]);
		add(a[i],tot,1,-bkt[a[i]]);add(1,a[i]-1,0,c);
		int mn=query(a[i],tot);
		cov(1,a[i]-1,mn);
	}
//	write(f[n][1]);
	write(query(1,tot));
	flush();
	return 0;
}

